A programmable logic circuit, also referred to as field programmable gate array (FPGA) is an off the shelf integrated logic circuit which can be programmed by the user to perform logic functions. Circuit designers define the desired logic functions and the circuit is programmed to process the signals accordingly. Depending on logic density requirements and production volumes, programmable logic circuits are superior alternatives in terms of cost and time to market. A typical programmable logic circuit is composed of logic cells where each of the logic cells can be programmed to perform logic functions on its input variables. Additionally, interconnect resources are provided throughout the programmable logic circuit which can be programmed to conduct signals from outputs of logic cells to inputs of logic cells according to user specification.
As technology progresses to allow for larger and more sophisticated programmable logic circuits, both the number of logic cells and the required interconnect resources increases in the circuit. Competing with the increased number of logic cells and interconnect resources is the need to keep the circuit size small. One way to reduce the required circuit size is to reduce the interconnect resources while maintaining a certain level of connectivity. Therefore, it can be seen that as the functionality implemented on the chip increases, the interconnection resources required to connect a large number of signals can be quickly exhausted. The trade-offs are either to provide for a lower utilization of logic cells in a circuit while keeping the circuit size small or to provide more routing resources that can increase the circuit size dramatically.
There has been steady attempts of using switching networks such as cross bar or Clos networks as the basis of an interconnection fabrics used in the field of programmable logic circuits. L. M. Spandorfer in 1965 describes possible implementation of a programmable logic circuit using neighborhood interconnection, and connections through multiple conductors using switches in a Clos network.
Reddy et al. in U.S. Pat. No. 6,417,694 discloses an architecture where inter-super-region, inter-region, and local conductors are used. A cross-bar scheme is used at the lowest level (using MUXs) for the local wires to have universal access to the inputs of the logic elements. Reddy et al. in U.S. Pat. No. 5,883,526 discloses various schemes having circuit reduction techniques in the local cross-bar.
Reblewski et al. in U.S. Pat. No. 6,594,810 describes an architecture building a programmable logic circuit using crossbar devices recursively. Wong in U.S. Pat. No. 6,693,456 and U.S. Pat. No. 6,940,308 use Benes switching networks as the interconnection fabric for programmable logic circuit.
At the base level of circuit hierarchy, multiple-input Look Up Table (LUT) logic cells are commonly used. There are two advantages in using a LUT as the base logic cell. One advantage is that the LUT allows programmable implementation of any Boolean functions having up to the multiple-input and one output. Another advantage is that the multiple inputs are interchangeable and logically equivalent. Hence, it does not matter which signal connecting to which input pin of the LUT for the LUT to function correctly as long as those signals connect to the respective inputs of the LUT.
A common problem to be solved in any programmable logic circuit is that of interconnectivity, namely, how to connect a first set of conductors or pins carrying signals to a second multiple sets of conductors to receive those signals where the logic cells originating the signals and the logic cells receiving the signals are spread over a wide area in an integrated circuit (i.e., M number of outputs from M or less number of logic cells where one or more outputs of each logic cells connects to inputs of one or more logic cells). A conventional solution is to use a cross bar switch where every conductor of the first set is connectable to every conductor in the second multiple sets of conductors directly through a switch. Unfortunately, this approach is impractical in most cases. Prior solutions in one degree or another try to divide the connectivity problem into multiple pieces using a divide and conquer strategy where local clusters of logic cells are interconnected and extended to other clusters of logic, either through extensions of local connections or using longer distance connections. These prior interconnect schemes are ad hoc and mostly based on empirical experiences. A desired routing model or interconnect architecture should enable or guarantee full connectivity for a large number of inputs and outputs over a large part of the circuit all the time.
U.S. Pat. No. 6,975,139, U.S. Pat. No. 7,256,614 and U.S. Pat. No. 7,417,457 by the present inventors describe one type of switching network (L-SN) of the conventional design in which the L-SN has (L+2) levels of conductors with L-level(s) of intermediate conductors of Ii number of conductors including D[i] sets of conductors for i=[1:L], L≧1 and Σi=[1:L+1](Ii−1×D[i]) number of switches where the 0-th level of pins or conductors of I0 number of pins or conductors selectively couple to the (L+1)-th level of pins or conductors of (D[L+1]×Πj=[1:L]D[j]) number of pins or conductors including D[L+1] sets of pins or conductors through the L level(s) of intermediate conductors and Σi=[1:L+1](Ii−1×D[i]) number of switches of the L-SN. A variable, DS[i] which is at least two, is defined as DS[i]=(Ii−1/Ii)×D[i] for i=[1:L+1]. A DS[i]-tuple is DS[i] number of conductors of the (i−1)-th level of conductors with the characteristics that the DS[i]-tuple selectively couple to one conductor, through a respective DS[i] number of switches, in each of the D[i] sets of conductors of the i-th level of conductors of the L-SN for i=[1:L+1]. Additionally, in the L-SN, the Ii−1 number of conductors of the (i−1)-th level can be organized into (Ii−1/DS[i]) groups of DS[i]-tuples for i=[1:L+1].
Two related patent applications by the present inventors, U.S. patent application Ser. No. 12/327,702 and U.S. patent application Ser. No. 12/327,704, disclosed alternative L-PSN with different switch coupling schemes operating on conductors between two consecutive levels of conductors where the permutable switching network (L-PSN) having Πj=[1:L+1](Ij−1×D[j]) number of switches and L-level(s) of intermediate conductors of Ii number of conductors having D[i] sets of conductors for i=[1:L] to connect the 0-th level of pins or conductors of I0 number of pins or conductors to the (L+1)-th level of pins or conductors of (D[L+1]×Πj=[1:L]D[j]) number of pins or conductors having D[L+1] sets of pins or conductors through the L level(s) of intermediate conductors and Σj=[1:L+1](Ij−1×D[j]) number of switches of the L-PSN with different switch coupling schemes from the conventional L-SN for L>1.
U.S. patent application Ser. No. 12/327,704 uses the same DS[i]-tuple definition in a L-PSN as those in the U.S. Pat. No. 6,975,139, U.S. Pat. No. 7,256,614 and U.S. Pat. No. 7,417,457. An L-PSN of this application uses the same DS[i]-tuple definition having the coupling characteristics of the DS[i]-tuples.
A weaker version of a DS[i]-tuple, denoted as W-DS[i]-tuple, is defined as DS[i] number of conductors of the (i−1)-th level of conductors which are selectively coupled to one conductor, through a respective DS[i] number of switches, in just one of the D[i] sets of conductors of the i-th level of conductors of the L-PSN for i=[1:L+1]. Thus a W-DS[i]-tuple which are selectively coupled to one of the D[i] sets of the Ii number of conductors can be different from any other W-DS[i]-tuple which are selectively coupled to a different set of the D[i] sets of conductors.
The labels Ii−1, Ii, DS[i], D[i] in FIG. 1A, FIG. 1B and FIG. 1C denote two levels of conductors Ii−1 and Ii with divider D[i] where DS[i]=D[i]×(Ii−1/Ii) in a conventional L-SN or L-PSN switching network described in U.S. patent application Ser. No. 12/327,702 and U.S. patent application Ser. No. 12/327,704 by the present inventors. For example, the labels Ii−1, Ii, DS[i], D[i] in FIG. 1A, FIG. 1B and FIG. 1C can be treated to respectively corresponds to the notations I0, I1, DS[1], D[1] of a conventional L-SN and L-PSN in U.S. patent application Ser. No. 12/327,702 and U.S. patent application Ser. No. 12/327,704 if we set i=1. Thus in the discussions of the embodiments of FIG. 1A through FIG. 1C below, those notations above are interchangeable.
As an illustration of the conventional designs, FIG. 1A illustrates one embodiment of the switch couplings between two consecutive levels of conductors in the conventional L-SN of U.S. Pat. No. 6,975,139, U.S. Pat. No. 7,256,614 and U.S. Pat. No. 7,417,457 where L>0: the (i−1)-th level of conductors of Ii−1=32 number of conductors, [101:132], selectively couple to the i-th level of conductors of Ii=32 number of conductors including D[i]=4 sets of (intermediate) conductors, {[151:158], [159:166], [167:174], [175:182]}; not every conductor of Ii−1 or Ii number of conductors are labeled in the embodiment of FIG. 1A, and for purpose of illustration, those conductors are assumed to be consecutively labeled. A DS[i]-tuple of the embodiment of FIG. 1A is of size four which is the same as the divider D[i] in this embodiment. The Ii−1 conductors [101:132] are selectively coupled to the first set of Ii conductors [151:158] through Ii−1 number of switches in 135; the Ii−1 conductors [101:132] are selectively coupled to the second set of Ii conductors [159:166] through Ii−1 number of switches in 140, the Ii−1 conductors [101:132] are selectively coupled to the third set of Ii conductors [167:174] through Ii−1 number of switches in 145 and the Ii−1 conductors [101:132] are selectively coupled to the D[i]-th set of Ii conductors [175:182] through Ii−1 number of switches in 150.
FIG. 1B illustrates one embodiment of the switch couplings between two consecutive levels of conductors in the conventional L-PSN of U.S. patent application Ser. No. 12/327,704 where L>0: the (i−1)-th level of conductors of Ii−1=32 number of conductors, [101:132], selectively couple to the i-th level of conductors of Ii=32 number of conductors including D[i]=4 sets of (intermediate) conductors, {[151:158], [159:166], [167:174], [175:182]} using the distribution sequence {Original, Prime 3, Prime 5, Prime 7}; not every conductor of Ii−1 or Ii number of conductors are labeled in the embodiment of FIG. 1B, and for purpose of illustration, those conductors are assumed to be consecutively labeled. A DS[i]-tuple of the embodiment of FIG. 1B is of size four which is the same as the divider D[i] in this embodiment. The Ii−1 conductors [101:132] are selectively coupled to the first set of Ii conductors [151:158] through Ii−1 number of switches in 135; the Ii−1 conductors [101:132] are selectively coupled to the second set of Ii conductors [159:166] through Ii−1 number of switches in 140, the Ii−1 conductors [101:132] are selectively coupled to the third set of Ii conductors [167:174] through Ii−1 number of switches in 145 and the Ii−1 conductors [101:132] are selectively coupled to the D[i]-th set of Ii conductors [175:182] through Ii−1 number of switches in 150.
FIG. 1C illustrates one embodiment of the switch couplings between two consecutive levels of conductors in the conventional L-PSN of U.S. patent application Ser. No. 12/327,702 where L>0: the (i−1)-th level of conductors of Ii−1=32 number of conductors, [101:132], selectively couple to the first level of conductors of Ii=32 number of conductors including D[i]=4 sets of (intermediate) conductors, {[151:158], [159:166], [167:174], [175:182]} using the distribution sequence {Prime 3, Prime 5, Prime 7, Prime 13}; not every conductor of Ii−1 or Ii number of conductors are labeled in the embodiment of FIG. 1C, and for purpose of illustration, those conductors are assumed to be consecutively labeled. A W-DS[i]-tuple of the embodiment of FIG. 1C is of size four which is the same as the divider D[i] in this embodiment; for example, (101, 104, 107, 110) of FIG. 1C would be a W-DS[i]-tuple coupling the first set of the Ii number of conductors. The Ii−1 conductors [101:132] are selectively coupled to the first set of Ii conductors [151:158] through Ii−1 number of switches in 135; the Ii−1 conductors [101:132] are selectively coupled to the second set of Ii conductors [159:166] through Ii−1 number of switches in 140, the Ii−1 conductors [101:132] are selectively coupled to the third set of Ii conductors [167:174] through Ii−1 number of switches in 145 and the Ii−1 conductors [101:132] are selectively coupled to the D[i]-th set of Ii conductors [175:182] through Ii−1 number of switches in 150.
In the conventional L-SN and L-PSN designs illustrated in FIG. 1A and FIG. 1B where nets 101 and 102 each carries the same signal connection specification (0), connecting to a pin in the 0-th K-port; nets 103 and 104 each carries the same signal connection specification (1), connecting to a pin in the 1st K-port (the part of switching network connecting to the K-ports are not illustrated in FIG. 1A or FIG. 1B); net 105 carries the signal connection specifications (0, 1), connecting to a respective pin in the 0-th K-port and the 1st K-port; with nets 106, 107 and 108 each carries the same signal connection specification (2), connecting to a pin in the 2nd K-port; it can be readily determined, for one skilled in the art, the nine pins in the eight nets cannot be fully connected using the respective switching network subject to the constraint that each of the set of Ii conductors of the D[i] number of sets carries at most one signal to each of the three K-ports [0:2].
Similarly, in the conventional L-PSN design illustrated in FIG. 1C where net 101 carries the signal connection specifications (0, 1, 2, 3), connecting to a respective pin in the 0-th K-port, the 1st K-port, the 2nd K-port and the third K-port; net 104 carries the signal connection specifications (1, 2, 3, 4); net 107 carries the signal connection specifications (2, 3, 4, 5); net 110 carries the signal connection specifications (3, 4, 5, 6); net 113 carries the signal connection specifications (0, 1, 5, 7); net 116 carries the signal connection specifications (0, 4, 6, 7); net 119 carries the signal connection specifications (1, 5, 6, 7) and net 122 carries the signal connection specifications (0, 2, 6, 7); it can be readily determined, for one skilled in the art, that there is no connection solution using the switching network where the first set of Ii number of conductors [151:158] of the D[i] sets of Ii conductors carries one signal to each of the eight K-ports [0:7] while each of the remaining three sets of the Ii number of conductors can be connected to the eight nets, (101, 104, 107, 110, 113, 116, 119, 122), such that each set of Ii number of conductors carries exactly eight signals, [0:7], to the K-ports using the switches of the switching network.